Cryptome DVDs are offered by Cryptome. Donate $25 for two DVDs of the Cryptome 12-years collection of 46,000 files from June 1996 to June 2008 (~6.7 GB). Click Paypal or mail check/MO made out to John Young, 251 West 89th Street, New York, NY 10024. The collection includes all files of cryptome.org, jya.com, cartome.org, eyeball-series.org and iraq-kill-maim.org, and 23,000 (updated) pages of counter-intelligence dossiers declassified by the US Army Information and Security Command, dating from 1945 to 1985.The DVDs will be sent anywhere worldwide without extra cost.

Google
 
Web cryptome.org cryptome.info jya.com eyeball-series.org cryptome.cn


31 October 1999
Source: Hardcopy of 37 pages from Anonymous. Original reportedly obtained from the National Security Agency by FOIA request.

This document is available Zipped (text and 13 images): http://cryptome.org/capstone.zip (298K).

See related declassified SKIPJACK-KEA specifications.

Redactions shown by xxxxxx or as indicated by number of lines or figures. Overstrikes in original.

Classification symbols: U = Unclassified; S = Secret; TS = Top Secret; Umbra = Codeword, a restricted Top Secret category; NF = No Release to Foreign Nationals; FOUO = For Official Use Only; OADR = Orginating Agency's Determination Required (for declassification).



TOP SECRET

R21 Informal Technical Report
R21-TECH-30-95
14 August 1995




CAPSTONE
(MYK-80) Specifications (U)

XXXXXXX R21




This Document is Classified TOP SECRET
and is Not Releasable to Foreign Nationals in
its entirety.

Classified by: NSA/CSSM 123-2
Delassify on: Originating Agency's Determination Required

THIS DOCUMENT CONTAINS
CODEWORD INFORMATION

Not Releasable to Foreign Nationals

TOP SECRET


[Each page with header and marked classified as shown on this page; hereafter omitted]

CAPSTONE (MYK-80) Specifications

TOP SECRET UMBRA




THIS PAGE INTENTIONALLY BLANK


Not Releasable to Foreign Nationals

TOP SECRET UMBRA




14 August 1995


CAPSTONE
(MYK-80) Specifications (U)

R21-TECH-30-95

ABSTRACT

(U) CAPSTONE started as an embodiment of a Law Enforcement SIGINT friendly replacement for the Data Encryption Standard (DES). This requirement would offer greater security than DES while permitting legitimate access to traffic. Given these restraints, the project goals were a commercially viable, single-chip solution offering data integrity, confidentiality, public key based key management and authentication. R21 undertook the development of an algorithm suited for CAPSTONE in support of the aforementioned requirements and goals.

(C) [Eight lines redacted.]

Written by: XXXXXXXX R211

Reviewed by: XXXXXXXX R213





THIS PAGE INTENTIONALLY BLANK



Table of Contents

I. Introduction

II. Algorithms

A. SKIPJACK Modes of Operation Specification
B. SKIPJACK Specification
C. KEA Specification
D. E-Mail Applications of KEA
E. Signature
F. Hash Specification

III. Anti-Reverse Engineering Circuitry and Techniques

A. VROM
B. Random Power Fluctuations

IV. Checkword Generation

A. CV checkword
B. Cover/Wrap Checkword

V. Cover/Uncover and Wrap Functions

VI. Key Escrow Circuitry

VII. Key Variable Storage and Loading

VIII. Randomization and Key Variable Generation

A. MI Generation
B. X, K and R Generation

IX. Synchronization

X. Zeroization

XI. Selected Analysis

A. KEA Analysis and Selection
B. E-Mail Analysis and Applications to a "Drop Box"

XII. Conclusion

XIII. Recommendation

Acronym List

References





THIS PAGE INTENTIONALLY BLANK



14 August 1995

CAPSTONE Specifications

I. Introduction

1. (U) Project CAPSTONE has been designed as the Next Generation Data Encryption Standard (DES2) for use by the Federal Government. Project CAPSTONE consists of an Integrated Circuit (IC) incorporating a suite of cryptographic algorithms necessary to provide confidentiality, data integrity and public key management. This IC is known as the CAPSTONE device or simply CAPSTONE.

2. (U) The details of the algorithms used in the CAPSTONE device are classified with the exception of the Digital Signature Standard and its associated appendices. When incorporated into hardware and installed in an approved device, the implementation is unclassified.

3. (C) [Nine lines redacted.]

CAPSTONE IC
(1.0 micron)

[Figure redacted.]

figure 1 "CAPSTONE IC Diagram"

II. Algorithms

1. (U) The CAPSTONE device incorporates the following CLASSIFIED algorithms:

SKIPJACK     Codebook Encryptor/Decryptor
KEA               Authenticated Key Exchange

CAPSTONE incorporates the following UNCLASSIFIED algorithms which have been published in Federal Information Processing Standards (FIPS).

DSA               The Digital Signature Algorithm
SHA               The Secure Hash Algorithm

CAPSTONE also contains all of the necessary randomization features necessary for the secure implementation of the above set of algorithms.

A. SKIPJACK Modes of Operation Specification

1. (U) CAPSTONE uses the SKIPJACK codebook for encryption. SKIPJACK is a 64 bit codebook utilizing an eighty bit cryptovariable. Modes of operation are a subset of the FIPS-81 description of modes of operation for DES. These include the following:

Output Feed-Back (OFB) Modes               64 bit.
Cipher Feed-Back (CFB) Modes               8, 16, 32, and 64 bit.
Codebook                                                   64 bit encrypt/decrypt modes.
Cipher-Driven Codebook (CDC)               64 bit encrypt/decrypt modes.

Note that the OFB and CFB modes of operation have been limited. This was an efficiency/memory trade-off that was made in order to conserve IC memory while providing a reasonable range of encryption rates. The modes are described in the following diagrams:



B. SKIPJACK Specification

1. (U) The MYKOTRONX implementations invoke a byte swap from the chip interface to the diagram description as shown below. The byte permutation for the state space is shown in the Table 1. The byte permutation for the load of cryptovariable are in Table 2. Note that the subscripts match the description. The bits within the bytes remain the same.

Table 1: Data I/O Byte Swap

   msb   

                                                     

   lsb   

d1 d2 d4 d4 d5 d6 d7 d8
b8 b7 b6 b5 b4 b3 b2 b1

TAble 2: CV Byte Swaps

   msb                                                                              lsb  
k0 k1 k2 k3 k4 k5 k6 k7 k8 k9
cv9 cv8 cv7 cv6 cv5 cv4 cv3 cv2 cv1 cv0

2. (S) U [U added by hand where shown following overstrike; omitted hereafter] SKIPJACK encrypts 8-byte messages by alternating between the two rules of motion (A and B) shown below. Since the G-function is a permutation on 16-bits, it requires two

bytes of input and produces two bytes of output. Therefore, in either rule of motion. a step will be defined to be a two-byte movement. A step of rule A does the following:

a. G permutes b1 and b2 as a word (b1 is the high-order byte and b2 is the low-order byte)

b. the new b1 is the xor of the high-order byte of the G output, the high-order byte of the counter, and b7

c. the new b2 is the xor of the low-order byte of the G output, the low-order byte of the counter, and b8

d. all of the bytes b3, b4, b5, b6 shift two places to the right (i.e.. b3 becomes b5, etc.)

e. the new b3 is the high-order byte of the G output

f. the new b4 is the low-order byte of the G output

g. the counter is incremented by one.

Rule B works similarly.

3. (S) U In the equations below. the superscript is the step number and the h and l subscripts for G and the counter represent the high and low order bytes of those quantities.

The inverse of rule A is closely related to rule B and the inverse of rule B is closely related to rule A. Nevertheless, for completeness, we give the full decrypt equations below.

We now describe separately the G-permutation, the stepping pattern, and the cryptovariable schedule.

4. (S) U G-permutation: The 16-bit cryptovariable-dependent G-permutation is built from an 8-bit fix permutation (called an F table) which is implemented as a 256-byte substitution table. G requires four F-table substitutions and four bytes of cryptovariable. We give three characterizations of the function below:

a. mathematically:

b. computer algorithmically:

Function G (high, low, step)
(* "high" and "low"' are the high and low order bytes of the word input: step is numbered from 0, i.e., step=counter-l *)

high = xor( F( xor( low, cv(4*step+0))), high)

low = xor( F( xor( high, cv(4*step+1))), low)

high = xor( F( xor( low, cv(4*step+2))), high)

low = xor( F( xor( high, cv(4*step+3))), low)

return (high, low)

Function G_inverse (high, low, step)

low = xor( F( xor( high, cv(4*step+3))), low)

high = xor( F( xor( low, cv(4*step+2))), high)

low = xor( F( xor( high, cv(4*step+1))), low)

high = xor( F( xor( low, cv(4*step+0))), high)

return (high, low)

c. schematically:

5. (S) [Nine lines redacted.]

6. (S) Cryptovariable schedule: the cryptovariable is 10 bytes long and used in its natural order. So the schedule subscripts given in the definition of the G-permutation are to be interpreted mod 10.

7. (S) U SKIPJACK F table is given below [compare to F-table at http://jya.com/skipjack-spec.htm ]

                  F-TABLE
a3 d7 09 83 f8 48 f6 f4 b3 21 15 78 99 b1 af f9 

e7 2d 4d 8a ce 4c ca 2e 52 95 d9 1e 4e 38 44 28 

0a df 02 a0 17 f1 60 68 12 b7 7a c3 e9 fa 3d 53 

96 84 6b ba f2 63 9a 19 7c ae e5 f5 f7 16 6a a2 

39 b6 7b 0f c1 93 81 1b ee b4 1a ea d0 91 2f b8 

55 b9 da 85 3f 41 bf e0 5a 58 80 5f 66 0b d8 90 

35 d5 c0 a7 33 06 65 69 45 00 94 56 6d 98 9b 76 

97 fc b2 c2 b0 fe db 20 e1 eb d6 e4 dd 47 4a 1d 

42 ed 9e 6e 49 3c cd 43 27 d2 07 d4 de c7 67 18 

89 cb 30 1f 8d c6 8f aa c8 74 dc c9 5d 5c 31 a4 

70 88 61 2c 9f 0d 2b 87 50 82 54 64 26 7d 03 40

34 4b 1c 73 d1 c4 fd 3b cc fb 7f ab e6 3e 5b a5 

ad 04 23 9c 14 51 22 f0 29 79 71 7e ff 8c 0e e2 

0c ef bc 72 75 6f 37 a1 ec d3 8e 62 8b 86 10 e8 

08 77 11 be 92 4f 24 c5 32 36 9d cf f3 a6 bb ac 

5e 6c a9 13 57 25 b5 e3 bd a8 3a 01 05 59 2a 46 

C. KEA Specification

1. (S-NF) U/FOUO [Six lines redacted.]

2. (S-NF) U KEA operations require exponents of length 160 bits. One exponent used in KEA is a user specific secret component which can be the same as that used for the DSS. As a matter of practicality, the use of the same public key certificate (i.e.. the same public key, private key pair along with the same 1024-bit modulus which has been certified by a trusted authority) is recommended but not required.

3. (S-NF) U The KEA provides security commensurate with that provided by SKIPJACK. This is on the order of 280 operations.

4. (U) The IC must have the SKIPJACK. We will denote this function with the following notation.

Eu(x) = the SKIPJACK encryption of message x (64 bits) using cryptovariable u.

5. (S-NF) U The IC must be provided the following data in order to implement the Key Exchange Algorithm (KEA).

p      1024-bit prime number which defines the field where
p = p1023 p1022 ... p0

g      1024-bit base for the exponentiation

g = g1023 g1022 ... g0

x      160-bit user secret number

x = x159 x158 ... x0

Y      1024-bit public value

Y = gx mod p = y1023 y1022 ... y0

r      160-bit random value

r = r159 r158 ... r0

pad   160 bit secret padding value

pad = pad159 pad158 ... pad0
    =
72f1a87e92824198ab0bf689042ee6577d9834fc hex.

The IC must also have a certificate signed by the Trusted Center which consists of the triple

(Y, sig1 , sig2)       where sig1 and sig2 are'the two 160-bit signature numbers.

6. (S-NF) U A description of the KEA process follows. For two users A and B, the subscripts A and B, are used to denote the 'owner' of the respective values. IC stands for the Integrated Circuit (i.e., the CAPSTONE device).

a. A and B exchange the signed packets (Y, sig1 , sig2) to the far terminal. Specifically, we have {(YA, sig1A , sig2A)} going to B and {(YB, sig1B , sig2B)} going to A. In addition. any ID information will be included with these packets and signed by the trusted authority.

b. Each device does a signature verification on the received packets to confirm that the value Y is that of a valid user on the network. If the verification fails. the process terminates. If the verification checks, go to step c.

c. Each device exchanges random components. ICA generates a 160-bit random number rA and sends

RA = grA mod p

ICB generates a 160-bit rB and sends

RB = grB mod p

Each of these random components is 1024 bits in length.

d. After receiving the far end random component and public key, each device will check to verify both the received values are of order q (where q divides p-1). ICA will compute and verify

RB not equal to 1 and YB not equal to 1

(RB)q = 1 mod p and (YB)q = 1 mod p

ICB will compute and verify

RA is not equal to 1 and YA is not equal to 1

(RA)q = 1 mod p and (YA)q = 1 mod p

If the verification checks, go to step e. Should the verification fail, stop.

e. ICA will take YB and compute the value tAB. ICB will do the same using the received random component

tAB = (YB)rA mod p = grAxB mod p = (RA)xB mod p = tBA

f. Each device computes

uAB = (YA)rB mod p = gxArB mod p = (RB)xA mod p = uBA

g. Each device checks to make sure that

w = tAB + uAB not equal to 0 mod p

If this check passes, go to step h. Else stop.

h. This result is split into two sections

v1 (w/2(1024 - 80)) mod 280     v2 (w/2(1024 - 160)) mod 280

i. The traffic key k is



D. E-Mail Applications of KEA

(S-NF) U For electronic mail applications where the recipient does not participate in the formation of the traffic key, the recipient's contribution to the random exchange is replaced with the public key of the recipient. For the following, let A be the sender and B be the recipient of the E-mail message We first begin with the formation of the E-mail message.

1. Sending E-Mail
a. A receives the signed packets (Y, sig1 , sig2) of the far terminal. Specifically, we have {(YB, sig1B , sig2B)} going to A. In addition, any ID information will be included with these packets.

b. Device A does a signature verification on the received packet to confirm that the value Y is that of a valid user on the network. If the verification fails, the process terminates. If the verification checks, go to step c.

c. Device A sends the random component. ICA generates a 160-bit random number rA and sends

RA = grA mod p

This random component is 1024 bits in length.

d. ICA will compute and verify.

YB is not equal to 1 and (YB)q = 1 mod p

If the verification checks, go to step e. Should the verification fail, stop.

e. ICA will take YB and compute the value tAB.

tAB = (YB)rA mod p = grAxB mod p

f. ICA computes

uAB = (YA)xA mod p = gxBxA mod p = gxAxB mod p

g. The sender computes

w = tAB + uAB

h. This result is split into two sections

v1 (w/2(1024 - 80)) mod 280     v2 (w/2(1024 - 160)) mod 280

i. The traffic key k is


2. Receiving E-Mail

a. B receives the signed packets (Y, sig1 , sig2) of the far terminal in the E-mail message. Specifically, we have {(YA, sig1A , sig2A)} going to B. In addition, any ID information will be included with these packets.

b. Device B does a signature verification on the received packet to confirm that the Y value is that of a valid user on the network. If the verification fails, the process terminates. If the verification checks, go to step c.

c. Device B receives the random component that A generated.

RA = grA mod p

This random component is 1024-bits in length.

d. ICB will compute and verify.

RA is not equal to 1 and YA is not equal to 1

(YA)q = 1 mod p and (RA)q = 1 mod p

If the verification checks, go to step e. Should the verification fail, stop.

e. ICB will take RA and compute the value tAB.

tAB = (RA)xB mod p = grAxB mod p

f. ICB computes

uAB = (YA)xB mod p = gxBxA mod p = gxAxB mod p

g. ICB checks to make sure that

w = tAB + uAB is not equal to 0 mod p

h. This result is split into two sections

v1 (w/2(1024 - 80)) mod 280     v2 (w/2(1024 - 160)) mod 280

i. The traffic key k is


E. Signature

1. (U) U/FOUO [Fourteen lines redacted.]

2. (U) [Eleven lines redacted.]

3. (U) Once a message to be signed becomes available, the steps in computing the actual signature values are as follows. First compute the following 160-bit integer

s2 = k-1 (h + (x) · (s1)) mod q

The values s1 and s2 constitute the signature of the message. The message, s1 and s2 are sent to the recipient where the signature can be verified. These are the values sig1 and sig2 in the KEA sections (s1 = sig1, s2 and sig2).

4. (U) In order to verify a signed message, a recipient must have the following global information:

p       The modulus being used by the signer.

Y       The public key for the user who signed the received message.

To verify the signature the recipient then computes the following:

The recipient then checks to see that v mod q is the same as s1. If they are equal the signature is verified.

F. Hash Specification

1. (U) U/FOUO [Nine lines redacted.]

2. (U) U/FOUO [Five lines redacted.]

3. (U) There are four functions, F = (f1, f2, f3, f4) used in the hash. Which function is used is dependent upon the internal step, t, of the SHA. Each is a mapping from V96 to V32 and is listed below in hexadecimal format.

4. (U) A series of constants, K = (k1, k2, k3, k4), are used in association with each function. These constants are listed below in hexadecimal format.

K = (5A827999, 6ED9EBA1, 8F1BBCDC, CA69C1D6)

5. (U) We define a function sY(X) to be

sY(X) = ((2Y(X) \/ (X/232-Y)) mod 232

If X is stored as a single 32 bit word with the bits arranged in decreasing order of significance from left to right, then this is equivalent to a circular shift of X by Y bit positions to the left.

6. (U) With these definitions, we can consider the diagram of SHA shown below:

SHA is stepped 80 times per message block. The values of A, B, C, D, and E are initialized with the intermediate hash values prior to stepping. After 80 steps, the contents of these registers are used to update the intermediate hash value registers by being added to the previous hash values, mod 232. This process repeats until all message blocks have been processed. The final contents of the intermediate hash value register is output as the hash.

III. Anti-Reverse Engineering Circuitry and Techniques

1. (S) [Five lines redacted.]

2. (TSC-NF) [Six lines redacted.]

3. (TSC-NF) [Seven lines redacted.]

A. VROM

1. (S) [Five lines redacted.]

2. (U) VROM is a one-time programmable technology developed by Quicklogic, Inc., which was licensed and improved by VLSI Inc. The original intent of the technology was to prevent non-destructive recovery of the memory cell contents of the VROM. The technology is essentially an "anti-fuse'' technique. Instead of using a voltage which physically opens a gap in metal conductor. a voltage is applied to amorphous silicon which causes the resistance of the silicon to be reduced. The amorphous silicon is sandwiched between two layers of metal. Thus a current channel is opened through the silicon (connecting the two metal layers) without physically altering the medium itself.

3. (S) [Three lines redacted.]

4. (S) [Nine lines redacted for items a, b, c, d, e, f and g.]

B. Random Power Fluctuations

1. (TSC-NF) [Six lines redacted.]

2. (S) [Four lines redacted.]

IV. Checkword Generation

A. CV checkword

1. (S) [Three lines redacted.]

B. Covert/Wrap Checkword

1. (S) U/FOUO [Three lines redacted.]

[Seventeen lines redacted.]

2. (S) [Seven lines redacted.]

V. Cover/Uncover and Wrap Functions

1. (S-NF) [Seven lines redacted.]

2. (S-NF) [Two lines redacted.]

3. (S-NF) [Eighteen lines redacted.]

4. (S-NF) [Twenty-six lines redacted.]

VI. Key Escrow Circuitry

1. (S U.S./Can Eyes Only) [Eight lines redacted.]

2. (S U.S./Can Eyes Only) [Fifty lines redacted.]

3. (S U.S./Can Eyes Only) [Three lines redacted.]

[Full (horizontal) page redacted.]

VII. Key Variable Storage and Loading

1. (S) [Three lines redacted.]

2. (S) [Three lines redacted.]

VIII. Randomization and Key Variable Generation

A.

1. (S-NF) [Forty-five lines redacted.]

B. X, K and R Generation

1. (U) U/FOUO [Seven lines redacted.]

2. (U) The following process describes the software randomization process. It assumes that the device in question possesses enough memory to store the 160 bit user secret terminal unique (X) and the seed value, (seed(Tau)), initially provided by the Local Authority (Central Authority). The device must also possess the capability to increment a 48 bit counter. The process is described below.

a) Read in X, (seed(Tau)) at power-up or beginning of each session.

b) If no X, (seed(Tau)) has been read in at power up and a random number is needed, then access the MI generation process 4 times.

(X, (seed(Tau)) = MI(t)//MI(t+l)//MI(t+2)//[MI(t+3)mod 232].

c) Initialize 45 bit counter to count = 1.

d) Is a random number needed? If not, wait. If so, go to step e.

e) Compute RN(t) = SHA(X, (seed(Tau)), count, RANDOM). This value can be used in either step g, h, or i, but cannot be used simultaneously in 2 or more of these steps.

f) Increment counter, count = (count +l ) mod 248. If count = 0, then alarm and to to step a.

g) If signature per message random number, k, is needed then k = RN(t) mod q. Go to step d.

h) If Key Exchange Random Number is needed then r = RN(t) mod q. Go to step d.

i) If new X variable is needed, then X = RN(t) mod q. Go to step d.

Should the host require an additional seed input. it is permissible to increment the seed and repeat this process until a new randomly generated seed is available. (i.e., seed(Tau) = (seed(Tau) + 1) mod 264)

IX. Synchronization

1. (S) [Three lines redacted.]

X. Zeroization

1. (S) [Three lines redacted.]

XI. Selected Analysis

1. (S) [Three lines redacted.]

A. KEA Analysis and Selection

1. (TSC-NF) [Twenty lines redacted.]

[Full page and one-half redacted.[

2. (S-NF) [Eighteen lines redacted.]

3. (TSC-NF) [Twenty-three lines redacted.]

4. (TSC-NF) [Two lines redacted.]

5. (TSC-NF) [Five lines redacted.]

6. (S-NF) [Ten lines redacted.]

7. (TSC-NF) [Twenty lines redacted for a, b and c and following.]

8. (TSC-NF) [Three lines redacted.]

XII. Conclusion

1. (S) [Four lines redacted.] cryptographic boundary.

2. (TSC-NF) [Six lines redacted.]

XIII. Recommendation

1. (TSC) [Four lines redacted.]

Acronyms

ARM6

CDC

CFB

CK

CV

CCV

DES

DMS

DSA

DSS

E-mail

EPROM

FIPS

IC

ID

ISSO

IV

KEA

LAW

XXX

MI

MOD

MSP

MYK-80

NIST

PMSP

RAM

RAND

RISC

ROM

SHA

SJ

TK

UK

VROM

Acorn RISC Machine 6

Cipher Driven Codebook

Cipher Feed Back

Cover Key

CryptoVariable

CryptoVariable

Data Encryption Standard

Defense Message Service

Digital Signature Algorithm

Digital Signature Standard

Electronic Mail

Electronically Programmable Read Only Memory

Federal Information Processing Standard

Integrated Circuit

Identity

Information Security Systems Organization

Initialization Vector

Key Exchange Algorithm

Local Authority Workstation

XXXXXXXXXXXXXXXXXXXX

Message Indicator

MODular arithmetic metacell (the exponentiator)

Message Security Protocol

MYKotronx Mark 80 chip

National Institute of Standards and Technology

Pre-Message Security Protocol

Random Access Memory

RANDomizer

Reduced Instruction Set Computer

Read Only Memory

Secure Hash Algorithm

SKIPJACK

Traffic Key

Unique Key

Vialink Read Only Memory


References

1. ''Secure Hash Standard." FIPS- 180: 1993 May 11: U.S. Department of Commerce, Technology Administration, National Institute of Standards and Technology.

2. "Escrowed Encryption Standard." FIPS PUB 185; 1994 February 9: U.S. Department of Commerce, Technology Administration, National Institute of Standards and Technology.

3. "DES Modes of Operation." FIPS PUB 81: U.S. Department of Commerce, Technology Administration, National Institute of Standards and Technology.

4. "Proposed Federal Information Processing Standard for Digital Signature Standard (DSS)." Federal Register. v.56, n.169: 30 August 1991.

5. "SKIPJACK (U)." R21-TECH-043-92: XXXX

DISTRIBUTION:

R T/Dir
R2
R2 T/Dir
R21
R211 XXXX





THIS PAGE INTENTIONALLY BLANK



TOP SECRET



[Blank rear cover]



THIS DOCUMENT CONTAINS
CODEWORD INFORMATION

Not Releasable to Foreign Nationals

TOP SECRET


Transcription and HTML by Cryptome.